/*
  COSC 560 
  File System Project
  Spring 2012
  Denise Koessler
  Nicholas Lineback
  Katie Schuman
*/
#include "FileSystem.h"
/* 
   Full description of Class variables in header file
*/

using namespace std;

/*
  FileSystem(bool defCache)
  constructor
  PARAMETERS: defCache - use caching
*/
  
FileSystem::FileSystem(bool defCache) {
	filesystemname = "";
	maxFileDesc = 0;            
	redirect = false;           
	defaultCacheBool = defCache;
	usecache = defCache;
}

/* 
   InitFileSystem(string fn)
   makes clean file system
   PARAMETERS: fn - name of file system file
*/
void FileSystem::InitFileSystem(string fn) {
	uint i, j;                          // loop variables
	uint contentAddr;                   // address of the first block we will write
//	char buff[MAX_INODES*INODE_SIZE];   // buffer for writing empty inode space
	char *buff;
	filesystemname = fn;
	usecache = false;                   // do not use caching
	buff = (char *)malloc(sizeof(char)*MAX_INODES*INODE_SIZE);
	
	
	// open file system file
	fp = fopen(fn.c_str(), "w+");
	if (fp == NULL) {
		// Print an error and exit
		cerr << "Cannot open " << fn << endl;
		exit(1);
	}
	// clear open files and unused file descriptors since this may not be the first
	// time we are making a file system
	openFiles.clear();
	unusedFileDesc.clear();
	maxFileDesc = 0;
	cache.CleanUp();
	// Operating under the assumption that the file doesn't exist
	// Add setup for the new file
	// WRITE A BUNCH OF ZEROS so that scratch space can be updated without causing file issues
	for (i = 0; i < MAX_INODES*INODE_SIZE; i++) {
		buff[i] = '0';
	}
	put(MAX_INODES*INODE_SIZE, 0, buff);

	// update scratch space values
	UpdateHeadOfFreeList(THE_END);
	UpdateNumberOfFreeBlocks(0);
	UpdateHeadOfInodeFreeList(THE_END);
	UpdateNumberOfFreeInodes(0);

	// write inode free list
	output << "Making inodes free..." << endl;
	for (i = INODE_SIZE; i < MAX_INODES*INODE_SIZE; i+=INODE_SIZE) {
		MakeInodeFree(i);
	}

	// write block free list
	output << "Making blocks free..." << endl;
	j = THE_END;
	for (i = FREE_LIST_HEAD+512; i < 104857600; i+=BLOCK_SIZE) {
		put(sizeof(uint), i, &j);
		MakeBlockFree(i);
	}		
	// Need a Write Inode Block for root
	usecache = defaultCacheBool;
	SetInodeData_ModTime(0, time(NULL));
	SetInodeData_NumLinks(0, 1);
	SetInodeData_FileSize(0, 0);
	SetInodeData_DirBit(0, 1);
	// get a free block for root
	contentAddr = AllocateBlock();
	if (contentAddr == THE_END) {
		cerr << "Issue in initializing file system." << endl;
		exit(1);
	}
	// set root data address
	SetInodeData_Address(0, contentAddr);	

	// write .. to root
	WriteToDirEntry(0, "..", 0);
	// set root and set current directory to root
	root = new Directory(0);
	currentDirectory = new Directory(0);
	free(buff);
}

/*
  destructor
*/
FileSystem::~FileSystem() {
	delete(root);
	delete(currentDirectory);
	cache.CleanUp();
	fclose(fp);
}
/* 
   SetInodeData_Address(uint inodeAddr, uint blockAddr)
   Set the first block of data pointed to by inode at inode address inodeAddr 
   to be blockAddr
   inodeAddr: the address of the inode
   blockAddr: the address of the block of first block
*/
void FileSystem::SetInodeData_Address(uint inodeAddr, uint blockAddr) {
	put(sizeof(uint), inodeAddr, &blockAddr);
}  
/*
  GetInodeData_Address(uint inodeAddr)
  Returns the first block of data pointed to by inode at inodeAddr
  Return: the first block of data pointed to by inode at inodeAddr
*/
uint FileSystem::GetInodeData_Address(uint inodeAddr) {
	uint ret;
	get(sizeof(uint), inodeAddr, &ret);
	return ret;
}
/* 
   SetInodeData_ModTime(uint inodeAddr, uint modTime)
   Set the modification time of the data pointed to by inode at inode address 
   inodeAddr to be modTime
   inodeAddr: the address of the inode to update
*/
void FileSystem::SetInodeData_ModTime(uint inodeAddr, time_t modTime) {
	put(sizeof(time_t), inodeAddr+MODTIME, &modTime);
}  
/*
  GetInodeData_ModTime(uint inodeAddr)
  Returns the modification time of the data pointed to by inode at inodeAddr
  inodeAddr: The address of the inode
  Return: the modification time of the data pointed to by inode at inodeAddr
*/
time_t FileSystem::GetInodeData_ModTime(uint inodeAddr) {
	time_t ret;
	get(sizeof(time_t), inodeAddr+MODTIME, &ret);
	return ret;
}
/* 
   SetInodeData_NumLinks(uint inodeAddr, uint numLinks)
   Set the number of links the to inode at inode address inodeAddr to be modTime
   inodeAddr: the address of the inode to update
   numLinks: the number of links
*/
void FileSystem::SetInodeData_NumLinks(uint inodeAddr, uint numLinks) {
	put(sizeof(uint), inodeAddr+NUMLINKS, &numLinks);
}
/*
  GetInodeData_NumLinks(uint inodeAddr)
  Returns the number of links  to the inode at inodeAddr
  inodeAddr: The address of the inode
  Return: the number of links to the inode at inodeAddr
*/
uint FileSystem::GetInodeData_NumLinks(uint inodeAddr) {
	uint ret;
	get(sizeof(uint), inodeAddr+NUMLINKS, &ret);
	return ret;
}
/* 
   SetInodeData_FileSize(uint inodeAddr, uint size)
   Set the size of the file pointed to by inode at inode address inodeAddr
   inodeAddr: the address of the inode to update
   size: the size of the file
*/
void FileSystem::SetInodeData_FileSize(uint inodeAddr, uint size) {
	put(sizeof(uint), inodeAddr+FILESIZE, &size);
}
/*
  GetInodeData_FileSize(uint inodeAddr)
  Returns the size of the file pointed to by the inode at inodeAddr
  inodeAddr: The address of the inode
  Return: file size of the file pointed to by the inode at inodeAddr
*/ 
uint FileSystem::GetInodeData_FileSize(uint inodeAddr) {
	uint ret;
	get(sizeof(uint), inodeAddr+FILESIZE, &ret);
	return ret;
}
/* 
   SetInodeData_DirBit(uint inodeAddr, char bit)
   Set whether or not the file pointed to by inode at inode address inodeAddr is a directory
   inodeAddr: the address of the inode to update
   bit: directory or not (1 for true 0 for no)
*/
void FileSystem::SetInodeData_DirBit(uint inodeAddr, char bit) {
	put(sizeof(char), inodeAddr+ISDIR, &bit);
}
/*
  GetInodeData_DirBit(uint inodeAddr)
  Returns whether the fil the file pointed to by the inode at inodeAddr
  inodeAddr: The address of the inode
  Return: 1 if the file is a directory 0 otherwise
*/
char FileSystem::GetInodeData_DirBit(uint inodeAddr) {
	char ret;
	get(sizeof(char), inodeAddr+ISDIR, &ret);
	return ret;
}
/*
  WriteBlankBlock(uint address, uint previous, uint next) 
  Writes a blank block
  address: the address of the block to be made blank
  previous: address of the previous block in the free list
  next: address of the next block in the free list
*/
void FileSystem::WriteBlankBlock(uint address, uint previous, uint next) {
	uint i;
	char buff[BLOCKCONTENTSIZE];  // buffer for writing 0's to content
	// write previous
	put(sizeof(uint), address, &previous);
	// write next
	put(sizeof(uint), address+4, &next);
	// fill buff with 0's and write to the block's content space
	for (i = 0; i < BLOCKCONTENTSIZE; i++) {
		buff[i] = '0';
	}
	put(BLOCKCONTENTSIZE, address+8, buff);	
}
/*
  WriteBlankInode(uint address, uint next) 
  Writes a blank inode
  address: the address of the inode to be made blank
  next: address of the next inode in the free list
*/
void FileSystem::WriteBlankInode(uint address, uint next) {
	uint i;
	char buff[28];       // buffer for writing 0's to content
	// write next
	put(sizeof(uint), address, &next);
	// fill buffer with 0's and write to content
	for (i = 0; i < 28; i++) {
		buff[i] = '0';
	}
	put(28, address+4, buff);
}
/*
  WriteBlankScratch() 
  Writes blank scratch
*/
void FileSystem::WriteBlankScratch() {
	char buff[496];   // buffer for 0's
	uint i;
	// fill buffer and write to scratch space
	for (i = 0; i < 496; i++) {
		buff[i] = '0';
	}
	put(496, BLANKSCRATCH, buff);
}
/*
  OpenFile(string filename, string flag)
  Opens file filename for reading or writing specified by flag and returns a 
  File pointer
  filename: name of the file
  flag: can be "r", "w", or "rw"
  Returns: a pointer to the open file object
*/
File* FileSystem::OpenFile(string filename, string flag) {
	File *f;        // pointer to the file object 
	int fd;         // the file descriptor
	uint inodeAddr; // the file's inode address

	// create a new file object with name filename and set its read/write flag
	f = new File(filename);
	if (flag == "r") f->rwflag = 0;
	else if (flag == "w") f->rwflag = 1;
	else if (flag == "rw") f->rwflag = 2;
	else {
		cerr << "Invalid file mode: must be r|w|rw" << endl;
		return NULL;
	}
	// create a file, not a directory
	// find the file's inode
	inodeAddr = FindFileInode(filename);
	// if the file does not exist the create it
	if (inodeAddr == THE_END) {	
		if(f->rwflag == 0){
			cerr << "File does not exist" << endl;
			return NULL;
		}
		inodeAddr = CreateFile(filename, 0);
		if(inodeAddr == THE_END){
			cerr << "Cannot create file: " << filename << endl;
			return NULL;
		}
	}
	// if the file is a directory print an error
	if (GetInodeData_DirBit(inodeAddr) == 1) {
		cerr << "Cannot open a directory." << endl;
		return NULL;
	}
	// if we have no unused file decriptors set fd to max and increase the max
	if (unusedFileDesc.empty()) {
		fd = maxFileDesc;
		maxFileDesc++;
	}
	// otherwise get the first unused file descriptor
	else {
		fd = *(unusedFileDesc.begin());
		unusedFileDesc.erase(unusedFileDesc.begin());
	}

	f->FID = fd;
	f->inodeAddr = inodeAddr;
	// add file to the open files
	openFiles.insert(make_pair(fd,f));
	return f;
}
/* CloseFile(int fd)
   close the file with file decriptor fd
   fd: the descriptor of the file to be closed
*/
void FileSystem::CloseFile(int fd) {
	// add file descriptor to unused file descriptors
	unusedFileDesc.insert(fd);
	// get a pointer to the file to be closed
	File* theFile = openFiles.find(fd)->second;
	// erase file from open files
	openFiles.erase(fd);
	// delete the file object
	delete theFile;
}
/*Write(int fd, string buff)
  Writes buff to open file with file descriptor fd if the file is open for writing and 
  prints errors if the file is not open or only open for reading
  fd: the file descriptor of the file to be written
  buff: a string with the data to be written
 */
void FileSystem::Write(int fd, string buff){
	// if fd is not in openFiles print an error and return
	if(openFiles.find(fd) == openFiles.end()){
		cerr << "File descriptor does not exist." << endl;
		return;
	}
	// get the pointer from open files
	File* theFile = openFiles.find(fd)->second;
	
	int i;

	// if the file is open for reading only print an error and return
	if (theFile->rwflag == 0) {
		cerr << "File is only open for reading." << endl;
		return;
	}
	// get inode address of the file
	uint inodeAddr = theFile->inodeAddr;
	// get the file size
	uint size = GetInodeData_FileSize(inodeAddr);
	// get the address of the first block of data for the file
	uint blockAddr = GetInodeData_Address(inodeAddr); 
	uint nextBlock; // next block of data
	// get the seek pointer for the file
	uint seekptr = theFile->seekptr;
	// amount of data left in the block
	uint rest = BLOCKCONTENTSIZE - (seekptr % BLOCKCONTENTSIZE);
	// the block that the seek pointer is in 
	uint numBlocks = seekptr / BLOCKCONTENTSIZE;
	uint actualSeek; // the actual seek in the entire file system
	uint bufferSize = buff.size(); // the size of the buffer
	char* cstringBuff; // a cstring buffer for writing
	cstringBuff = (char*)malloc(buff.size());
	// if there are not enough block left to write buffer print an error
	if (bufferSize/BLOCKCONTENTSIZE + 2+MINFREEBLOCKS > NumberOfFreeBlocks()) {
		cerr << "Do not have enough blocks to complete write." << endl;
		return;
	}
	// seek to block that we want to begin writing
	for(int i = 0; i < numBlocks; i++){
		get(sizeof(uint), blockAddr+4, &nextBlock);
		blockAddr = nextBlock;
	}
	// calculate the actual seek in the file system 
	actualSeek = blockAddr + 8 + seekptr % BLOCKCONTENTSIZE;
	// copy buff to cstring
	strcpy(cstringBuff, buff.c_str());
	// if buff is smaller than the rest of the block write it
	if(buff.size() <= rest){
		put(buff.size(), actualSeek, cstringBuff);
	}
	// if buff is larger than the rest of the block
	else{
		// copy enough of the buffer to fill the rest of the current block
		strcpy(cstringBuff, buff.substr(0,rest).c_str());
		// fill the rest of the current block
		put(rest, actualSeek, cstringBuff);
		// strip what was just written off of the buffer
		buff = buff.substr(rest);
		// while we still have data in the buffer
		while(buff.size() != 0){
			// get the address of the next block of data
			get(sizeof(uint), blockAddr+4, &nextBlock);
			// if the next block is THE_END allocate another block
			if(nextBlock == THE_END){
				nextBlock = AllocateBlock();
				// if the next block is THE_END there are no more 
				// blocks to allocate so print an error
				if (nextBlock == THE_END) {
					cerr << "Could not complete write." << endl;
					return;
				}
				// set previous field of next block to the current block address
				put(sizeof(uint), nextBlock, &blockAddr);
				// set next field of current block to next block
				put(sizeof(uint), blockAddr + 4, &nextBlock);
			}
			// set the current block to be the next block
			blockAddr = nextBlock;
			// if buffer size is less then the size of a block
			if(buff.size() <= BLOCKCONTENTSIZE){
				// copy buff to cstring
				strcpy(cstringBuff, buff.c_str());
				// write buffer to block 
				put(buff.size(), blockAddr + 8, cstringBuff);
				// clear the buffer
				buff = "";
			}
			// if buffer is bigger than a block
			else{
				// copy enough of the buffer to fill a block 
				strcpy(cstringBuff, buff.substr(0,BLOCKCONTENTSIZE).c_str());
				// fill the block
				put(BLOCKCONTENTSIZE, blockAddr + 8, cstringBuff);
				// strip a block of the front of the buffer
				buff = buff.substr(BLOCKCONTENTSIZE);
			}
		}
	}
	// move the seek pointer
	theFile->seekptr += bufferSize;
	// if the seek pointer did not move past the end of the file the file is the same size
	// otherwise it is the size of seekptr
	size = (theFile->seekptr > size) ? theFile->seekptr : size;
	// set the file size in the inode
	SetInodeData_FileSize(inodeAddr, size);
	// if the size of the file lands on the end of a block, allocate another block for next time
	if(size%BLOCKCONTENTSIZE == 0){
		// allocate a block
		nextBlock = AllocateBlock();
		// if there are no more blocks print an error
		if (nextBlock == THE_END) {
			cerr << "Could not complete write" << endl;
			return;
		}
		// update next and previous fields of connected blocks
		put(sizeof(uint), nextBlock, &blockAddr);
		put(sizeof(uint), blockAddr + 4, &nextBlock);
	}
	// set the modification time
	SetInodeData_ModTime(inodeAddr, time(NULL));
	free(cstringBuff);
}
/* Read(uint fd, uint size)
   Returns: a buffer of size size read from the current seek pointer of the open file with file 
   descriptor fd, if the file is either not open or not open for reading returns NULL and 
   prints an error
   fd: the file descriptor for the file to be read
   size: the amount of data to be read
 */
char * FileSystem::Read(uint fd, uint size){
	// if the file descriptor is not in open files, print an error and return
	if(openFiles.find(fd) == openFiles.end()){
		cerr << "File descriptor does not exist." << endl;
		return NULL;
	}
	// get a pointer to the open file with file descriptor fd
	File* theFile = openFiles.find(fd)->second;
	// if the file is not open for reading print an error and return NULL
	if (theFile->rwflag == 1) {
		cerr << "File not opened for reading" << endl;	
		return NULL;
	}	
	// get file inode address
	int inodeAddr = theFile->inodeAddr;
	// get file size
	int fileSize = GetInodeData_FileSize(inodeAddr);
	// get address of first block in file
	int blockAddr = GetInodeData_Address(inodeAddr);
	int nextBlock; // the next block of data
	// get the position of the file seek pointer
	int seekptr = theFile->seekptr;
	// if the size to read is more than the amount left in file
	// print an error and return NULL
	if (size > fileSize - seekptr){
		cerr << "Cannot read past end of the file" << endl;
		return NULL;
	}
	// calculate how much space is left in current block
	int rest = BLOCKCONTENTSIZE - (seekptr % BLOCKCONTENTSIZE);
	// calculate the block that the seek pointer is in
	int numBlocks = seekptr / BLOCKCONTENTSIZE;
	int actualSeek;  // the address in the entire file system
	int pos = 0;     // postion relative to start of read
	char* buff;      // buffer to read into
    // allocate the buffer
	buff = (char*)malloc(sizeof(char)*(size+1));

	// seek to appropriate block
	for(int i = 0; i < numBlocks; i++){
		get(sizeof(uint), blockAddr+4, &nextBlock);
		blockAddr = nextBlock;
	}
	// calculate the postion in the file system 
	actualSeek = blockAddr + 8 + seekptr % BLOCKCONTENTSIZE;

	// if the size to read is less than or equal to 
	// the amount to read, read it into buffer
	if(size <= rest){
		get(size, actualSeek, buff);
	}
	// if the size to read is greater than the size to read
	else{
		// get the rest in the current block
		get(rest, actualSeek, buff);
		// update postion in read buffer
		pos += rest;
		// while we haven't read it all 
		while(pos < size){
			// get the address of the next block
			get(sizeof(uint), blockAddr+4, &nextBlock);
			// set current block to next block
			blockAddr = nextBlock;
			// update the actuall position in the file system
			actualSeek = blockAddr + 8;
			// the rest is the min of a block or how much is left to read
			rest = (BLOCKCONTENTSIZE > size - pos) ? size - pos : BLOCKCONTENTSIZE;
			// read the rest into buffer
			get(rest, actualSeek, buff + pos);
			// update position
			pos += rest;
		}
	}
	// add a null character to the end
	buff[size] = '\0';
	// update seek pointer
	theFile->seekptr += size;
	return buff;
}
/*
  ProcessCommand(string command)
  process command 
  command: the command to process
 */
uint FileSystem::ProcessCommand(string command) {
	istringstream ss(command); // string stream for parsing command
	vector <string> fields;    // tokens in command 
	string s;                  // temp string for parsing
	uint inodeAddr, parentInode; // parent inode address and inode address
	// parse command
	while (ss >> s) {
		fields.push_back(s);
	}
	// if mkfs make new file system
	if (fields[0] == "mkfs") {
		// if file system is already made, close the file
		if (filesystemname != "") {	
			fclose(fp);
		}
		// initialize new file system
		InitFileSystem("nkdfs.txt");
	}
	// if we are not making a new file system
	else { 
		// quit the file system
		if (fields[0] == "quit") {
			return -1;
		}
		// exit from sh
		else if (fields[0] == "exit") {
			return 0;
		}
		// otherwise we have some action to perform on the file system
		else {
			// if we have not made a file system
			if (filesystemname == "") {
				cerr << "Error: Must create a file system" << endl;
			}
			// open a file 
			if (fields[0] == "open") {
				// check for appropriate syntax
				if (fields.size() != 3) {
					cerr << "syntax: open filename r|w|rw" << endl;
				}
				else {	
					// open the file
					File *f = OpenFile(fields[1], fields[2]);
					// if no errors
					if (f != NULL ) {
						output << "File opened successfully: file descriptor = " << f->FID << endl;
					}
				}
			}
			// read a file
			else if (fields[0] == "read") {
				// check syntax
				if (fields.size() != 3) {
					cerr << "syntax: read file_descriptor num_of_bytes" << endl;
				}
				else {
					// read bytes in to buffer
					char *buff = Read(atoi(fields[1].c_str()),atoi(fields[2].c_str()));
					// if no errors
					if (buff != NULL){
						string printable = buff;
						// insert into output stream
						output << printable << endl;
						free(buff);
					}
				}
			}
			// write to a file
			else if (fields[0] == "write") {
				// check syntax
				if (fields.size() < 3) {
					cerr << "syntax: write file_descriptor text_to_be_written_in_quotes" << endl;
				}
				else {
					int i;
					// makes sure the thing to be written is delimited by double quotes
					if (command[command.size()-1] != '\"' || 
						command.find("\"") == string::npos || 
						command.find_first_of("\"") == command.size() - 1) {
						cerr << "syntax: write file_descriptor text_to_be_written_in_quotes" 
							 << endl << "You forgot to include quotes!" << endl;
					}
					else {
					s = command.substr(1 + command.find("\""));
					s = s.substr(0,s.length() - 1);
					// preprocess string to write by converting "\\n" to "\n"
					while (s.find("\\n") != string::npos) {
						i = s.find("\\n");
						s.replace(i, 2, "x");
						s[i] = '\n';
					}
					// write to file
					Write(atoi(fields[1].c_str()),s);
					}
				}
			}
			// move seek pointer in a file
			else if (fields[0] == "seek") {
				// check syntax
				if (fields.size() != 3) {
					cerr << "syntax: seek file_descriptor num_to_seek" << endl;
				}
				else {
					// move seek pointer
					SeekFile(atoi(fields[1].c_str()), atoi(fields[2].c_str()));

				}
			}
			// close file
			else if (fields[0] == "close") {
				// check syntax
				if (fields.size() != 2) {
					cerr << "syntax: close file_descriptor" << endl;
				}
				else {
					// close file
					CloseFile(atoi(fields[1].c_str()));
				}
			}
			// make a directory
			else if (fields[0] == "mkdir") {
				// check syntax
				if (fields.size() != 2) {
					cerr << "syntax: mkdir dir_name" << endl;
				}
				else {
					// create a file as a directory
					inodeAddr = CreateFile(fields[1], 1);
					// check for errors
					if(inodeAddr == THE_END){
						cerr << "Cannot create directory: " << fields[1] << endl;
					}
					else{
						// write '..' to directory 
						uint parentDir = FindParentInode(fields[1]);	
						WriteToDirEntry(inodeAddr, "..", parentDir);
					}
				}
			}
			// remove a directory
			else if (fields[0] == "rmdir") {
				// check syntax
				if (fields.size() != 2){
					cerr << "syntax: rmdir dir_name" << endl;
				}
				else{
					// find the inode
					inodeAddr = FindFileInode(fields[1]);
					// check for errors
					if (inodeAddr == THE_END) {
						cerr << "Directory does not exist." << endl;
					}
					// check if it is parent directory
					else if (fields[1] == ".."){
						cerr << "Cannot remove parent directory!" << endl;
					}
					else{
						// the directory must be empty to be removed
						if(GetInodeData_FileSize(inodeAddr) != 36){
							cerr << "Directory must be empty!" << endl;
						}
						else{
							// unlink the directory
							unlink(fields[1], true);
						}
					}
				}
			}
			// change directory
			else if (fields[0] == "cd") {
				// check syntax
				if (fields.size() != 2) {
					cerr << "syntax: cd dir_name" << endl;
				}
				// special case if changing to root
				else if( fields[1] == "/"){
					currentDirectory->inodeAddress = root->inodeAddress;
				}
				else {
					// find the file's inode
					if (fields[1][fields[1].size()-1] == '/') fields[1] = fields[1].substr(0, fields[1].size()-1);
					inodeAddr = FindFileInode(fields[1]);
					// check for errors
					if (inodeAddr == THE_END) {
						cerr << "Directory does not exist." << endl;
					}
					// change the current directory's inode address
					else {	
						currentDirectory->inodeAddress = inodeAddr;
					}
				}
			}
			// link a file
			else if (fields[0] == "link") {
				// check syntax
				if (fields.size() != 3) {
					cerr << "syntax: link src dest" << endl;
				}

				else {
					// find the inode
					inodeAddr = FindFileInode(fields[1]);
					// check for errors
					if (inodeAddr == THE_END) {
						cerr << "Source file does not exist." << endl;
					}
					// if the file is a directory, we do not allow that
					else if(GetInodeData_DirBit(inodeAddr) == 1){
						cerr << "Cannot link a directory!" << endl;
					}
					// if the file is not a directory
					else {
						// find its parent
						parentInode = FindParentInode(fields[2]);
						// strip off path information 
						if (fields[2].find("/") != string::npos)
							fields[2] = fields[2].substr(fields[2].find_last_of('/')+1);	
						// write new directory entry
						WriteToDirEntry(parentInode, fields[2], inodeAddr);
						// set update inode information 
						SetInodeData_NumLinks(inodeAddr, GetInodeData_NumLinks(inodeAddr)+1);
						SetInodeData_ModTime(inodeAddr, time(NULL));
					}
				}
			}
			// unlink a file
			else if (fields[0] == "unlink") {
				// check syntax
				if(fields.size() != 2){
					cerr << "syntax: unlink file_name" << endl;
				}
				// unlink file
				else {
					unlink(fields[1], false);
				}
			}
			// print inode info
			else if (fields[0] == "stat") {
				// check syntax
				if (fields.size() != 2) {
					cerr << "syntax: stat file_name" << endl;
				}
				
				else {
					// print the info
					PrintInodeInfo(fields[1]);
				}
			}
			// list 
			else if (fields[0] == "ls") {
				ListFiles();
			}
			// cat a file
			else if (fields[0] == "cat") {
				// check syntax
				if (fields.size() != 2) {
					cerr << "syntax: cat file_name" << endl;
				}	
				// print the file
				else {
					CatFile(fields[1]);
				}
			}
			// copy a file
			else if (fields[0] == "cp") {
				// check syntax
				if (fields.size() != 3) {
					cerr << "syntax: cp src dest" << endl;
				}	
				else {
					// find the inode of the file to copy
					inodeAddr = FindFileInode(fields[1]);
					// check for errors
					if (inodeAddr == THE_END) {
						cerr << fields[1] << " does not exist." << endl;
					}
					// if the file is a directory we do not support that
					else if (GetInodeData_DirBit(inodeAddr) == 1) {
						cerr << "Cannot copy a directory" << endl;
					}
					else {
						uint destAddr = FindFileInode(fields[2]);
						// if the file already exists we do not over write
						if (destAddr != THE_END) {
							cerr << fields[2] << " already exists." << endl;
						}
						else {
							// create the new file
							destAddr = CreateFile(fields[2], 0);
							// check for errors
							if(destAddr == THE_END){
								cerr << "Cannot create file: " << fields[2] << endl;
							}
							else{
								// open source for reading
								File * srcFile = OpenFile(fields[1], "r");
								// open destination for writing
								File *destFile = OpenFile(fields[2], "w");
								// read source into buffer
								char *buff = Read(srcFile->FID, GetInodeData_FileSize(inodeAddr));
								// if no errors reading source write buffer to dest and close both files
								if (buff != NULL){
									s = buff;
									Write(destFile->FID, s); 
									CloseFile(srcFile->FID);
									CloseFile(destFile->FID);
									free(buff);
								}
							}
						}			
					}
				}
			}
			// print a tree from the current directory
			else if (fields[0] == "tree") {
				Tree(currentDirectory->inodeAddress,"");
			}
			// import a file
			else if (fields[0] == "import") {
				// check syntax
				if (fields.size() != 3) {
					cerr << "syntax: import src dest" << endl;
				}
				else {
					// import file
					ImportFile(fields[1], fields[2]);
				}
			}
			// export a file
			else if (fields[0] == "export") {
				// check syntax
				if (fields.size() != 3) {
					cerr << "syntax: export src dest" << endl;
				}
				else {
					// export file
					ExportFile(fields[1], fields[2]);
				}
			}
			// run a shell script
			else if (fields[0] == "sh") {
				// check syntax
				if ((fields.size() != 5 && fields.size() != 3) || fields[1] != "<" || (fields.size() == 5 && fields[3] != ">")) {
					cerr << "syntax: sh < inputfile OR sh < inputfile > outputfile" << endl;
				}
				else {
					// if no output redirection 
					if (fields.size() == 3) {
						Shell(fields[2], "");
					}
					// if there is output redirection
					else {
						Shell(fields[2], fields[4]);
					}
				}
			}
			else if (fields[0] == "exit") { }
			// else it is an invalid command
			else {
				cerr << "Error: Invalid Command" << endl;
			}
		}
	}
	// if redirection is not on
	if (!redirect) {
		// use cout and clear string stream
		cout << output.str();
		output.str("");
	}
}

/* Shell(string infile, string outfile)
infile: The input file with a list of commands to execute.
outfile: The output file to write all output to.  If outfile = "", 
output is not redirected to a file.
*/
void FileSystem::Shell(string infile, string outfile) {
	uint inodeAddr;		// Inode address of input file
	File *f;		// Input file
	string command;		// Current command to process
	uint size;		// Size of input file
	char *buff;		// Input file read into buffer
	string s;		// Contains the contents of the input file

	// Find the inode address of the input file. Print an error
	// if file does not exist
	inodeAddr = FindFileInode(infile);
	if (inodeAddr == THE_END) {
		cerr << infile << " does not exist!" << endl;
		return;
	}

	// Open input file for reading, find the size, read in the entire
	// file into a buffer, and convert the buffer to a C++ string. 
	f = OpenFile(infile, "r");
	size = GetInodeData_FileSize(inodeAddr);
	buff = Read(f->FID, size);
	CloseFile(f->FID);
	s = buff;
	
	// Strip off the first command (read to the newline)
	command = s.substr(0, s.find_first_of("\n"));
	s = s.substr(s.find_first_of("\n")+1);
	
	// Check for output redirection, if so, set redirection boolean to
	// to true so that output can be tracked.
	if (outfile != "") {
		redirect = true;	
	}
	// While there is a command to process, call ProcessCommand()
	while (command != "") {
		if (command != "")
			if (ProcessCommand(command) == -1)
				break;
		// Strip off the next command
		command = s.substr(0, s.find_first_of("\n"));
		if (s.find_first_of("\n") != string::npos) {
			s = s.substr(s.find_first_of("\n")+1);
		}
		// If there are no more newlines, there aren't any more commands
		// left in the input file.
		else {
			s = "";
		}
	}

	free(buff);

	// If there is an output file, open it, write all of the output, and close it.
	if (outfile != "") {
		f = OpenFile(outfile, "w");
		Write(f->FID, output.str());
		CloseFile(f->FID);
		redirect = false;
		output.str("");
	}
}

/* ExportFile(string src, string dest)
src: the file in our file system that will be written to the host
machine file system.
dest: the name of the file on the host file system that will be written
*/
void FileSystem::ExportFile(string src, string dest) {
	uint inodeAddr;		// inode address of the source file
	FILE *ofp;		// FILE pointer to the destination 
				// file on host machine
	File *f;		// Internal file pointer to the source file
	char *buff; 		// buffer that source's contents will be read into	

	// Find the inode address of the source file, print an error
	// if the source file does not exist.
	inodeAddr = FindFileInode(src);
	if (inodeAddr == THE_END) {
		cerr << src << " does not exist." << endl;
		return;
	}
	// Check to make sure the source isn't a directory
	if (GetInodeData_DirBit(inodeAddr) == 1) {
		cerr << "Cannot export a directory." << endl;
		return;
	}
	// Attempt to open the destination file for reading.
	// If the file already exists on the host machine, will
	// NOT overwrite it.
	ofp = fopen(dest.c_str(), "r");
	if (ofp != NULL) {
		cerr << dest << " already exists." << endl;
		fclose(ofp);
		return;
	}
	// Open the file on the host machine for writing.
	ofp = fopen(dest.c_str(), "w");
	
	// Open source file read in its contents and close it.
	f = OpenFile(src, "r");
	buff = Read(f->FID, GetInodeData_FileSize(inodeAddr));
	CloseFile(f->FID);

	// Write the contents of the buffer to the destination file and close it
	fwrite(buff, sizeof(char), GetInodeData_FileSize(inodeAddr), ofp);
	fclose(ofp);
	free(buff); 
}

/* ImportFile(string src, string dest) 
src: name of the file on the host file system to import
dest: name of the new file created in our file system
*/ 
void FileSystem::ImportFile(string src, string dest) {
	uint fileSize;		// size of the file to import
	char *buff;		// contents of the file
	FILE *ifp;		// FILE * (for host file system) for the source file
	uint inodeAddr;		// inode address of destination file in our system
	File *f;		// internal file pointer for destination file
	string s;		// contents of file to be written to dest in C++ string form

	// Open file for read, check for existence, and print an error if does not exist.
	ifp = fopen(src.c_str(), "r");
	if (ifp == NULL) {
		cerr << src << " does not exist." << endl;
		return;
	}
	// Make sure that destination file does not already exist. If it does,
	// print an error. 
	inodeAddr = FindFileInode(dest);
	if (inodeAddr != THE_END) {
		fclose(ifp);
		cerr << dest << " already exists." << endl;
		return;	
	}	
	// Find the file size of the source file
	fseek(ifp, 0, SEEK_END);
	fileSize = ftell(ifp);
	fseek(ifp, 0, SEEK_SET);
	
	// Allocate enough space to read in entire file from host system and read it in
	buff = (char *)malloc(sizeof(char)*(fileSize));
	fread(buff, sizeof(char), fileSize - 1, ifp);
	buff[fileSize - 1] = '\0';

	// Create destination file, checking for file creation errors
	inodeAddr = CreateFile(dest, 0);
	if(inodeAddr == THE_END){
		cerr << "Cannot create file: " << dest << endl;
		return;
	}

	// Open the destination file for writing, convert char * to string
	// so Write() can be used, and then close file
	f = OpenFile(dest, "w");
	s = buff;
	Write(f->FID, s);
	CloseFile(f->FID);
	
	// Clean up
	fclose(ifp);
	free(buff);
} 

/* CatFile(string filename)
filename: the file to concatenate in the shell
*/
void FileSystem::CatFile(string filename) {
	File *f;		// internal file pointer for filename
	uint inodeAddr;		// inode address of filename
	uint size;		// size of filename
	char *buff;		// holds contents of filename
	string printable;	// string form of buff, so it can be printed
	
	// Search for file inode, print an error if it does not exist.
	inodeAddr = FindFileInode(filename);
	if (inodeAddr == THE_END) {
		cerr << filename << " does not exist." << endl;
		return;
	}

	// Make sure file is not a directory
	if (GetInodeData_DirBit(inodeAddr) == 1) {
		cerr << "Cannot cat a directory" << endl;
		return;
	}
	// Open file for reading, read in contents to buffer
	f = OpenFile(filename, "r");
	buff = Read(f->FID, GetInodeData_FileSize(inodeAddr));
	
	// Convert to a buffer to a printable string and output the result.
	printable = buff;
	output << printable << endl;

	// Clean up
	free(buff);
	CloseFile(f->FID);	
}

/* PrintInodeInfo(string filename)
filename: the file whose info is printed
*/
void FileSystem::PrintInodeInfo(string filename) {
	uint inodeAddr;	// inode address of filename
	time_t t;	// Modification time of filename
	uint fileSize;	// size of file specified by filename
	
	// Find the associated inode, print an error if it doesn't exist.
	inodeAddr = FindFileInode(filename);
	if (inodeAddr == THE_END) {
		cerr << filename << " does not exist." << endl;
		return;
	}

	// Print the inode address
	output << "Inode Address: " << inodeAddr << endl;
	
	// Print whether the file is a directory or a file
	if (GetInodeData_DirBit(inodeAddr) == 0) {
		output << filename << " is not a directory" << endl;
	}
	else {
		output << filename << " is a directory" << endl;
	}

	// Print the number of links
	output << "Links: " << GetInodeData_NumLinks(inodeAddr) << endl;

	// Print the size of the file
	fileSize = GetInodeData_FileSize(inodeAddr);
	output << "File Size: " << fileSize << endl;

	// Print the number of blocks for that file.
	output << "Number of blocks: " << fileSize/BLOCKCONTENTSIZE+1 << endl;

	// Print the last modification time
	t = GetInodeData_ModTime(inodeAddr);
	output << "Last modified: " << ctime(&t) << endl;	
}

/* ListFile()
Lists the contents of the current directory.
*/
void FileSystem::ListFiles() {
	uint dirContentsAddr;	// address of the directory entry of the current directory
	uint currentLine;	// current line being processed in the directory entry
	uint totalFiles;	// number of files in the current directory
	uint size;		// size of the current directory's directory entry
	uint numBlocks;		// number of blocks required by the current directory's
				// directory entry
	char buffer[33];	// buffer to hold the file name being processed
	string checkName;	// string to hold the file name being processed
	uint i, j, k, x;	// loop variables
	set <string> toPrint;	// files to print, sorted in alphabetical order 
	set <string>::iterator sit;	// iterator for toPrint

	// Find information about size of directory entry, number of blocks,
	// and total number of files.
	dirContentsAddr = GetInodeData_Address(currentDirectory->inodeAddress);
	size = GetInodeData_FileSize(currentDirectory->inodeAddress);
	numBlocks = size/BLOCKCONTENTSIZE+1;	
	totalFiles = size/36;
	currentLine = dirContentsAddr+8;
	k = 0;
	
	
	// Go through each line of the directory entry, adding files to toPrint set.
	for (i = 0; i < numBlocks; i++) {		
		for (j = 0; j < 14 && k < totalFiles; j++, k++)  {
			// Get the current filename and convert it to a string.
			get(32, currentLine, buffer);
			buffer[32] = '\0'; 	// in case the filename is a full 32 bytes
			x = 0;
			while (buffer[x] != '\0') {
				checkName.push_back(buffer[x]);
				x++;
			}
			// Print it if it's .., insert it into toPrint otherwise.
			if (checkName == "..") output << checkName << endl;
			else toPrint.insert(checkName);
			currentLine += 36;
			checkName = "";	
		}
		if (k >= totalFiles) break;
		get(sizeof(uint), dirContentsAddr+4, &dirContentsAddr);
		currentLine = dirContentsAddr+8; 
	}
	// Print out files in alphabetical order
	for (sit = toPrint.begin(); sit != toPrint.end(); sit++) {
		output << *sit << endl;
	}
} 

/* FindParentInode(string filename)
filename: relative or absolute path of a file
Returns: the inode address of the file's parent directory, if
the parent directory exists, THE_END otherwise.
*/
uint FileSystem::FindParentInode(string filename) {
	uint curdir;	// inode address of directory being processed
	string d;	// name of directory being processed 

	// Check for absolute or relative path and update curdir accordingly
	if (filename[0] == '/') {
		// Absolute path
		curdir = root->getInodeAddress();
		filename = filename.substr(1); 
	}	
	else {
		// Relative path
		curdir = currentDirectory->getInodeAddress();
	}
	while (filename.find_first_of('/') != string::npos) {
		// Strip off the directory at the beginning of path
		d = filename.substr(0, filename.find_first_of('/'));
	
		// Look in the directory entry specified by current directory's 
		// inode address, and look for d -- return the inode address 
		// associated with d 
		curdir = FindAssocInodeAddress(curdir, d); 
		if (curdir == THE_END) return THE_END;
		// Strip the directory name just processed off of filename
		filename = filename.substr(filename.find_first_of('/')+1);
	}
	return curdir;
}

/* MakeBlockFree(uint blockAddr)
blockAddr: the address of the block that is to be made free
*/
void FileSystem::MakeBlockFree(uint blockAddr) {
	uint nextBlock;		// address of the block specified as the next block
	uint prevBlock;		// address of the block specified as the previous block
	uint i;			// temporary variable for storing THE_END
	// If some block points to blockAddr, it needs to be updated
	// to point to nothing (since blockAddr is being freed)
	get(sizeof(uint), blockAddr, &prevBlock);
	if (prevBlock != THE_END) {
		i = THE_END;
		put(sizeof(uint), prevBlock+4, &i);
	}

	// Find current head of free list
	nextBlock = HeadOfFreeList();

	// Update new free block to point to old head of free list
	// and fill it with zeros
	WriteBlankBlock(blockAddr, THE_END, nextBlock);

	// Update old free list head to point back to new block
	if (nextBlock != THE_END) {
		put(sizeof(uint), nextBlock, &blockAddr);
	}
	// Update head of free list and total number of free blocks
	UpdateHeadOfFreeList(blockAddr);
	UpdateNumberOfFreeBlocks(NumberOfFreeBlocks()+1);
}

/* MakeInodeFree(uint blockAddr)
blockAddr: address of inode to be made free
*/
void FileSystem::MakeInodeFree(uint blockAddr) {
	uint nextBlock;		// current head of free list, before entering function
	nextBlock = HeadOfInodeFreeList();
	
	// Update new free block to point to old head of free list,
	// and fill blank inode with zeros.
	WriteBlankInode(blockAddr, nextBlock);

	// Update head of inode free list and the total number of free inodes.
	UpdateHeadOfInodeFreeList(blockAddr);
	UpdateNumberOfFreeInodes(NumberOfFreeInodes()+1);
}

/* AllocateBlock()
Returns: address of newly allocated block, if a block is available,
and returns THE_END if no block is available
*/
uint FileSystem::AllocateBlock() {
	uint blockAddr;		// newly allocated block address
	uint nextBlock;		// block pointed to by block address (new head of free list)
	uint i;			// temporary variable holding THE_END
	uint numFree;		// Current number of free blocks

	// Make sure there is a block to allocate, if not print an error.
	numFree = NumberOfFreeBlocks();
	if (numFree == 0) {
		cerr << "No free blocks. Consider removing files or directories to free up blocks." << endl;
		return THE_END;
	}

	// Block returned will be the old head of the free list
	blockAddr = HeadOfFreeList();

	// Find the block pointed to be block address to be new free list head
	get(sizeof(uint), blockAddr+4, &nextBlock);
	UpdateHeadOfFreeList(nextBlock);

	// Update number of free blocks (decrement it by 1)
	UpdateNumberOfFreeBlocks(numFree-1); 
	
	// Update block's next pointer to be THE_END (as it no longer points to anything)
	i = THE_END;
	put(sizeof(uint), blockAddr+4, &i);

	return blockAddr;
}

/* AllocateInode()
   Returns: the address of the newly allocated inode, if an inode was available,
   and THE_END if no inode is available
*/
uint FileSystem::AllocateInode() {
	uint blockAddr;		// address of inode being allocated
	uint nextBlock;		// will be new head of inode free list
	uint numFree;		// total number of free inodes

	// Find number of free inodes and print an error if none left
	numFree = NumberOfFreeInodes();
	if (numFree == 0) {
		cerr << "No free inodes. Consider removing files or directories to free up inodes." << endl;
		return THE_END;
	}
	// Find the current head and the inode it points to
	blockAddr = HeadOfInodeFreeList();
	get(sizeof(uint), blockAddr, &nextBlock);

	// Update the inode free list head to be the inode
	// pointed to by the previous free list head
	UpdateHeadOfInodeFreeList(nextBlock);

	// Update number of free blocks.
	UpdateNumberOfFreeInodes(numFree-1);
	return blockAddr; 
}

/* WriteToDirEntry(uint dirInode, string filename, uint inodeAdd)
dirInode: the inode address of the directory being written to
filename: the filename to write to the new directory
inodeAdd: the inode address of the file name to be written
*/
void FileSystem::WriteToDirEntry(uint dirInode, string filename, uint inodeAdd) {
	uint blockAddr;			// address of directory entry's block
	uint nextBlock;			// the address of the next block in list 
					        // after blockAddr
	uint dirContentSize;		// current directory contents size
	char fn[MAXFILENAMESIZE];	// will hold filename
	uint i;				// loop and temporary variable

	// Error check filename size
	if (filename.size() > 32) {
		return;
	}
	// Make sure we have enough free blocks left to complete write
	if (NumberOfFreeBlocks() < MINFREEBLOCKS+1) {
		cerr << "Not enough blocks to complete write to directory entry. Consider deleting files or directories to free blocks." << endl;
		return;
	} 
	
	// Find the size of the directory entry
	dirContentSize = GetInodeData_FileSize(dirInode);

	// Figure out the last block of all blocks making up the 
	// directory entry
	blockAddr = GetInodeData_Address(dirInode);

	get(sizeof(uint), blockAddr+4, &nextBlock);

	while (nextBlock != THE_END ) {
		blockAddr = nextBlock;
		get(sizeof(uint), blockAddr+4, &nextBlock);
	}
	// Copy the contents of filename into fn, and pad it up to 32
	// with null characters 
	strcpy(fn, filename.c_str());
	for (i = filename.size(); i < MAXFILENAMESIZE; i++) {
		fn[i] = '\0';
	}
	// At this point in time, blockAddr holds the address of the last block
	// in the directory entry
	// i holds the address of the very end of the contents of the current block
	// which is where the new filename will be written.
	i = blockAddr+8+dirContentSize%BLOCKCONTENTSIZE;
 
	// Write filename and associated inode address
	put(MAXFILENAMESIZE, i, fn); 
	put(sizeof(uint), i+MAXFILENAMESIZE, &inodeAdd);

	// Update directory's size and modification time
	SetInodeData_FileSize(dirInode, dirContentSize+MAXFILENAMESIZE+4);
	SetInodeData_ModTime(dirInode, time(NULL));

	// If we have filled up the last block, allocate a new empty block
	if ((dirContentSize+MAXFILENAMESIZE+4)%BLOCKCONTENTSIZE == 0) {
		nextBlock = AllocateBlock();
		// Set current end of chain to point to the newly allocated block
		put(sizeof(uint), blockAddr+4, &nextBlock);
		// Set the newly allocated block to point back
		put(sizeof(uint), nextBlock, &blockAddr);	
	}	
}

/* unlink(string fileName, bool dir)
fileName: name of file to unlink
bool: whether or not the file is expected to be a directory
(unlink() is called by "rmdir" as well as "unlink" to avoid
reuse of the exact same code)
*/
void FileSystem::unlink(string fileName, bool dir){
	uint 
		inodeAddr,	// inode address of file specified by fileName
		parentInode,	// inode address of the file's parent directory
		numLinks,	// number of links in the file's inode
		blockAddr,	// address of blocks containing file contents
		nextBlock; 	// next block in chain of file content blocks
	uint j;			// temporary variable holding THE_END
	// Find the inode address of the file and print an error 
	// if it does not exist
	inodeAddr = FindFileInode(fileName);
	if(inodeAddr == THE_END){
		cerr << "File does not exist!" << endl;
		return;
	}

	// If the file is a directory and it was not expected to be
	// a directory, an error is printed.
	if(GetInodeData_DirBit(inodeAddr) == 1 && !dir){
		cerr << "Cannot unlink a directory. Consider using rmdir." << endl;
	}

	// Find the parent inode, and remove the file from
	// the parent's directory entry.
	parentInode = FindParentInode(fileName);
	RemoveFileFromDirEntry(parentInode, fileName, inodeAddr);

	// Find the number of links
	numLinks = GetInodeData_NumLinks(inodeAddr);
	if (numLinks != 1){
		// Removing the current file will not cause the number
		// of links to go to zero, so just update number of links
		// and modification time
		SetInodeData_NumLinks(inodeAddr, numLinks - 1);
		SetInodeData_ModTime(inodeAddr, time(NULL));
		return;
	}
	else{
		// The number of links is current one, so removing it
		// will cause the contents to be deleted.

		// Find the first block of contents and what it points to
		blockAddr = GetInodeData_Address(inodeAddr);
		get(sizeof(uint), blockAddr+4, &nextBlock);
		// Free first block
		MakeBlockFree(blockAddr);
		// Free each of the block contents
		while (nextBlock != THE_END ) {
			blockAddr = nextBlock;
			get(sizeof(uint), blockAddr+4, &nextBlock);
			j = THE_END;
			// Make sure that the current block points BACK to 
			// nothing as its previous block was just erased
			put(sizeof(uint), blockAddr, &j);
			// Free current block
			MakeBlockFree(blockAddr);
		}
		// Free the inode
		MakeInodeFree(inodeAddr);
	}			
}

/* RemoveFileFromDirEntry(uint dirInode, string filename, uint inodeAddr)
dirInode: inode of the directory file is being removed from
filename: name of the file to be removed
inodeAddr: inode address of the file being removed
*/
void FileSystem::RemoveFileFromDirEntry(uint dirInode, string filename, uint inodeAdd) {
	uint dirContentsAddr;	// address of a block of the directory contents
	uint currentLine;	// address of current line in directory contents
	uint lineToReplace;	// address of line containing filename
	uint lastLine;		// address of last line of directory contents
	uint totalFiles;	// total files in directory entry
	uint size;		// total size of directory entry
	uint numBlocks;		// number of blocks in directory entry
	char buffer[33];	// buffer to hold file names read in
	string checkName;	// string to hold file names read in
	uint i, j, k, x;	// loop variables

	// Find first block of directory entry
	dirContentsAddr = GetInodeData_Address(dirInode);
	currentLine = dirContentsAddr+8;

	// Find information about size of directory entry, number of blocks,
	// number of files.
	size = GetInodeData_FileSize(dirInode);
	numBlocks = size/BLOCKCONTENTSIZE+1;	
	totalFiles = size/36;
	
	k = 0;

	// Check each line (where a line is a filename and inode address), looking for 
	// the file that is to be removed, as wel as the last file.
	for (i = 0; i < numBlocks; i++) {

		for (j = 0; j < 14 && k < totalFiles; j++, k++)  {
			get(32, currentLine, buffer);
			buffer[32] = '\0'; 	// in case the filename is a full 32 bytes
			x = 0;
			// Put the buffered file name into a string
			while (buffer[x] != '\0') {
				checkName.push_back(buffer[x]);
				x++;
			}

			// If the file is the one to be removed, keep its address in
			// lineToReplace
			if (checkName == filename) {
				lineToReplace = currentLine;
			}
			// If its the last file, keep its address in lastLine
			if (k == totalFiles - 1){
				lastLine = currentLine;
			}

			currentLine += 36;
			checkName = "";	
		}
		//if (found) break;
		get(sizeof(uint), dirContentsAddr+4, &dirContentsAddr);
		currentLine = dirContentsAddr+8; 
	}
	// Read the lastLine contents into buffer and its inode address into k
	get(32, lastLine, buffer);
	get(4, lastLine + 32, &k);
	// Replace the file name being removed with the file name last in the
	// directory entry (to fill holes in the directory entry)
	put(32, lineToReplace, buffer);
	put(4, lineToReplace + 32, &k);
	uint nextBlock;
	// If the old size of the block was totally full, there was an empty 
	// block attached to it, waiting to be filled.
	// This block needs to be freed.
	if(size % 504 == 0) {
		// Find the address of the empty block
		dirContentsAddr = GetInodeData_Address(dirInode);
		get(sizeof(uint), dirContentsAddr+4, &nextBlock);
		while (nextBlock != THE_END) {
			dirContentsAddr = nextBlock;
			get(sizeof(uint), dirContentsAddr+4, &nextBlock);
		}
		// Make the last block free
		MakeBlockFree(dirContentsAddr);
	}
	// Update modification time and file size of the directory entry.
	SetInodeData_ModTime(dirInode, time(NULL));
	SetInodeData_FileSize(dirInode, size - 36);
	return;
}

/* SeekFile(uint fd, uint offset)
fd: file descriptor of the file whose seek pointer will be updated.
offset: how far from the beginning the seek pointer should be set
*/
void FileSystem::SeekFile(uint fd, uint offset) {
	File *f;	// internal file pointer of the file
	// Make sure the descriptor makes sense
	if (openFiles.find(fd) == openFiles.end()) {
		cerr << "No such file descriptor exists." << endl;
		return;
	}
	
	// Find the associated file pointer and update its seek pointer.
	f = openFiles.find(fd)->second;
	f->seekptr = offset;
}

/* CreateFile(string filename, char isdir)
filename: name of file to be created (may be a path)
isdir: 0 if is a file, 1 if it is to be a directory
(CreateFile() is called for "mkdir" also)
Returns: inode address of the newly created file on success,
THE_END on error
*/
uint FileSystem::CreateFile(string filename, char isdir) {
	uint inodeAdd;		// inode address of file created
	uint blockAdd;		// block address of file contents of newly created file
	uint i;			// temporary holder for THE_END
	uint curdir;		// address of parent directory's inode


	// Find the inode address of the parent directory of the filename specified.
	// Print an error and return if no such parent directory exists.	
	curdir = FindParentInode(filename);
	if (curdir == THE_END) {
		cerr << "Cannot create: parent directory does not exist" << endl;
		return THE_END;
	}
	// Strip off path information of filename, if it is there.
	filename = filename.substr(filename.find_last_of('/')+1);

	// Make sure file name does not exceed 32 characters.	
	if(filename.size() > 32){
		cerr << "File name exceeds 32 characters." << endl;
		return THE_END;
	}
	// Make sure there is an inode to allocate.
	if (NumberOfFreeInodes() < 1+MINFREEBLOCKS) {
		cerr << "Not enough inodes to create file. Consider deleting files or directories to free inodes." << endl;
		return THE_END;
	}
	// Make sure there is a block to allocate.
	if (NumberOfFreeBlocks() < 1+MINFREEBLOCKS) {
		cerr << "Not enough blocks to create file. Consider deleting files or directories to free blocks." << endl;
		return THE_END;
	}
	
	// Allocate inode and block for new file
	inodeAdd = AllocateInode();
	blockAdd = AllocateBlock();
	
	// Write filename to appropriate directory's directory entry 
	WriteToDirEntry(curdir, filename, inodeAdd);
	// Set all of the information in the new inode
	SetInodeData_ModTime(inodeAdd, time(NULL));
	SetInodeData_NumLinks(inodeAdd, 1);
	SetInodeData_FileSize(inodeAdd, 0);
	SetInodeData_DirBit(inodeAdd, isdir);
	SetInodeData_Address(inodeAdd, blockAdd);
	// Update block contents to point to nothing, both forward and backward.
	i = THE_END;
	put(sizeof(uint), blockAdd, &i);
	get(sizeof(uint), blockAdd + 4, &i);

	return inodeAdd;	
}

/* NumberOfFreeBlocks()
Returns: the current number of free blocks in the file system
*/
uint FileSystem::NumberOfFreeBlocks() {
	uint numFree;	// number of free blocks
	get(sizeof(uint), FREE_LIST_COUNT, &numFree);
	return numFree;
}

/* NumberOfFreeInodes()
Returns: the number of free inodes in the file system
*/
uint FileSystem::NumberOfFreeInodes() {
	uint numFree;	// number of free inodes
	get(sizeof(uint), INODE_FREE_LIST_COUNT, &numFree);
	return numFree;
} 

/* HeadOfFreeList()
Returns: the address of the block that is at the head of the free list
*/
uint FileSystem::HeadOfFreeList() {
	uint head;	// address of block at head of free list	
	get(sizeof(uint), FREE_LIST_HEAD, &head);
	return head;

}

/* HeadOfInodeFreeList()
Returns: the address of the inode that is at the head of the inode free list
*/
uint FileSystem::HeadOfInodeFreeList() {
	uint head;	// address of inode at head of free inode list
	get(sizeof(uint), INODE_FREE_LIST_HEAD, &head);
	return head;
}

/* get(uint size, uint loc, void *buffer)
size: number of bytes to read in
loc: location to start reading from in file
buffer: where to put the read in bytes (assumed to be previously allocated 
to proper size)
*/
void FileSystem::get(uint size, uint loc, void *buffer) {
	uint offset = loc%BLOCK_SIZE;	// how far into the block containing loc is loc 
	uint blockAddr = loc-offset;	// address of block contains loc
	char *block;			// Contents of block (used for cache info)
	
	// If the cache is being used
	if (usecache) {
		// Look for block in cache
		block = cache.FindBlock(blockAddr);
		if (block == NULL) {
			// If block is not in cache
			// Read the entire block in
			fseek(fp, blockAddr, SEEK_SET);
			block = (char *)malloc(sizeof(char)*BLOCK_SIZE);
			fread(block, 1, BLOCK_SIZE, fp);	
			// Insert it into cache
			cache.InsertBlock(blockAddr, block);			
		}
		else {
			// In cache, so update its last used time
			cache.TouchBlock(blockAddr);
		}
		// Copy from the block(starting at loc) in cache to buffer
		memcpy(buffer, block+offset, size); 
	}
	// If not using cache, read directly from file
	else {
		fseek(fp, loc, SEEK_SET);
		fread(buffer, 1, size, fp);
	}
}
/* put(uint size, uint loc, void *buffer)
size: number of bytes to write to file/cache
loc: address to write the bytes to in file
buffer: the contents to write
*/
void FileSystem::put(uint size, uint loc, void *buffer) {
	uint i;	 			// error checking value
	uint offset = loc%BLOCK_SIZE;	// how far into the block containing loc is loc
	uint blockAddr = loc-offset;	// which block contains loc
	char *block;			// contents of the block in cache
	// Update the file accordingly (done always, regardless of cache
	// to keep the file consistent with the system
	fseek(fp, loc, SEEK_SET);
	i = fwrite(buffer, 1, size, fp);
	if (i != size) {
		cerr << "Problem writing to file" << endl;
		exit(1);
	}
	// If using cache, it needs to be updated
	if (usecache) {
		// Find block in the cache
		block = cache.FindBlock(blockAddr);
		if (block == NULL) {
			// If it's not in the cache, the entire block needs to be read in
			fseek(fp, blockAddr, SEEK_SET);
			block = (char *)malloc(sizeof(char)*BLOCK_SIZE);
			fread(block, 1, BLOCK_SIZE, fp);
			cache.InsertBlock(blockAddr, block);
		}	
		else {
			// If it is in the cache, the block needs to be updated
			// and its last access time needs to be updated (for LRU)
			memcpy(block+offset, buffer, size);
			cache.TouchBlock(blockAddr);
		}
	}
}

/* FindFileInode(string filename)
filename: search for the inode of the file specified by filename
Returns: the inode of the file, or THE_END if the file does not exist
 */
uint FileSystem::FindFileInode(string filename) {
	// Find the parent directory, if it doesn't exist, return THE_END
	uint parentDir = FindParentInode(filename);
	if (parentDir == THE_END) return THE_END;
	// Strip off the any directory info ahead of the filename
	if (filename.find("/") != string::npos){
		filename = filename.substr(filename.find_last_of("/")+1);
	}
	// Find the filename in the current directory and return its inode
	// If not there, FindAssocInodeAddress() returns THE_END 
	uint fileInode = FindAssocInodeAddress(parentDir, filename);
	return fileInode;
}

/* FindAssocInodeAddress(uint curDirInodeAddress, string filename) 
curDirInodeAddress: the inode address of the directory that will be searched for filename
filename: the name of the file that 
Returns: the inode address of the filename specified, if it exists, THE_END if
the file does not exist in the directory specified by curDirInodeAddress
 */
uint FileSystem::FindAssocInodeAddress(uint curDirInodeAddress, string filename) {
	uint dirContentsAddr;	// Address of the current directory entry content block
	uint currentLine;	// Address of the current line being processed
	uint totalFiles;	// Total number files in the directory
	uint size;		// Total size of the directory entry in bytes
	uint numBlocks;		// Total number of blocks used by the directory entry
	char buffer[33];	// File name to check against filename (C style)
	string checkName;	// File name to check against filename (C++ style)
	uint inode;		// Inode number to return	
	uint i, j, k, x;	// Loop variables

	// Find the address of the first block containing the directory listing 
	get(sizeof(uint), curDirInodeAddress, &dirContentsAddr);	
	size = GetInodeData_FileSize(curDirInodeAddress);

	// Find the total number of files in the directory 
	numBlocks = size/BLOCKCONTENTSIZE+1;	
	totalFiles = size/36;
	currentLine = dirContentsAddr+8;
	k = 0;

	// Traverse the files in the directory entry, searching for file name
	for (i = 0; i < numBlocks; i++) {		
		for (j = 0; j < 14 && k < totalFiles; j++, k++)  {
			get(32, currentLine, buffer);
			// In case the filename is a full 32 bytes
			buffer[32] = '\0'; 	
			x = 0;
			while (buffer[x] != '\0') {
				checkName.push_back(buffer[x]);
				x++;
			}

			// Found the file name, so read in its inode number and return
			if (checkName == filename) {
				get(sizeof(uint), currentLine+32, &inode);
				return inode;	
			}
			currentLine += 36;
			checkName = "";	
		}
		if (k >= totalFiles) break;
		get(sizeof(uint), dirContentsAddr+4, &dirContentsAddr);
		currentLine = dirContentsAddr+8; 
	}
	// Did not find the file in the specified directory entry, so return THE_END
	return THE_END;
}

/* UpdateNumberOfFreeBlocks(uint number) 
number: the count of free blocks in the file system is updated to this number
 */
void FileSystem::UpdateNumberOfFreeBlocks(uint number) {
	put(sizeof(uint), FREE_LIST_COUNT, &number);
}

/* UpdateHeadOfFreeList(uint address)
address: the head of the block free list is updated to this address
 */
void FileSystem::UpdateHeadOfFreeList(uint address) {
	put(sizeof(uint), FREE_LIST_HEAD, &address);
}

/* UpdateNumberOfFreeInodes(uint number)
number: the count of free inodes in the file system is updated to this number
 */ 

void FileSystem::UpdateNumberOfFreeInodes(uint number) {
	put(sizeof(uint), INODE_FREE_LIST_COUNT, &number);
}

/*
   UpdateHeadOfInodeFreeList(uint address)
address: the head of the inode free list is updated to be this value 
 */
void FileSystem::UpdateHeadOfInodeFreeList(uint address) {
	//	cerr << "Updating head of inode list: " << address << endl;
	put(sizeof(uint), INODE_FREE_LIST_HEAD, &address);
}

/* 
   Tree():
curDirInodeAddress: inode address of the directory that is currently
being listed.
printSpaces: string of spaces to print ahead of the listed items
(used to achieve proper indentation)
 */

void FileSystem::Tree(uint curDirInodeAddress,string printSpaces){
	uint dirContentsAddr;	  	// Holds the block address of the directory entry
	uint isDir;			// Used to check to see if directory entry is a directory
	uint curdir;			// Current directory inode address
	uint currentLine;		// Address of current line being processed
	uint totalFiles;		// Total files in the directory entry
	uint size;			// Size of the directory entry
	uint numBlocks;			// Total number of blocks for the directory entry
	char buffer[33];		// Holds the filename read in (in C string)
	string checkName;		// Holds the filename read in (in C++ string)
	//	uint inode;			
	uint i, j, k, x;		// Loop variables
	set <string> toPrint;		// Holds all file names to print, so that they can be printed in alphabetical order
	set <string>::iterator sit;	// Iterator for toPrint

	// Find the address of the first block containing the directory listing 
	dirContentsAddr = GetInodeData_Address(curDirInodeAddress);

	// Find the total number of files in the directory 
	size = GetInodeData_FileSize(curDirInodeAddress);
	numBlocks = size/BLOCKCONTENTSIZE+1;	
	totalFiles = size/36;

	// Set the current line to be the first line of the first block
	// (skipping the first 8 bytes indicating previous and next block
	currentLine = dirContentsAddr+8;
	k = 0;
	// Find all of the files/directories in the current directory and 
	// insert them into a set (so they will be printed in order)
	for (i = 0; i < numBlocks; i++) {		
		for (j = 0; j < 14 && k < totalFiles; j++, k++)  {
			get(32, currentLine, buffer);
			// In case the filename is a full 32 bytes
			buffer[32] = '\0'; 	
			x = 0;
			// Add all the non-null characters to a string
			while (buffer[x] != '\0') {
				checkName.push_back(buffer[x]);
				x++;
			}
			// Avoid recursively calling Tree() on the parent directory
			if (checkName != "..") toPrint.insert(checkName);
			// Skip past the file name just read in and its associated inode
			currentLine += 36;
			checkName = "";	
		}
		if (k >= totalFiles) break;
		// Find the address of the next block of contents and update the current line to point to the first file name in that block.
		get(sizeof(uint), dirContentsAddr+4, &dirContentsAddr);
		currentLine = dirContentsAddr+8; 
	}

	for (sit = toPrint.begin(); sit != toPrint.end(); sit++) {
		output << printSpaces << *sit << endl; 
		// Check to see if checkName is a directory, if so, call tree on it, adding extra spaces to print in front of its contents
		isDir = FindFileInode(*sit);
		if(GetInodeData_DirBit(isDir)== 1){
			curdir = currentDirectory->inodeAddress;
			// Temporarily set the current directory to be the directory Tree() is called on
			currentDirectory->inodeAddress = isDir;
			Tree(isDir,printSpaces+"     ");
			// Reset the current directory to be the actual current directory
			currentDirectory->inodeAddress = curdir;
		}
	}
}
